#include <unordered_map>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        /*
        //最小堆
        unordered_map<int,int> table;
        for(auto i:nums){
            table[i]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        for(auto j:table){
            pair<int,int> tmp(j.second,j.first);
            if(pq.size()==k){
                if(pq.top()>tmp){
                    continue;
                }
                pq.pop();
            }
            pq.push(tmp);
        }
        vector<int> ret(k);
        int j=k-1;
        while(!pq.empty()){
            ret[j]=pq.top().second;
            cout<<pq.top().second<<endl;
            j=j-1;
            pq.pop();
        }
        return ret;
        */

        //桶排序
        if(nums.size()==k){
            return nums;
        }
        unordered_map<int,int> table;
        for(auto i:nums){
            table[i]++;
        }
        vector<vector<int>> fre(nums.size()+1);
        for(auto j:table){
            fre[j.second].push_back(j.first);
        }
        /*
        for(int i=0;i<fre.size();i++){
            cout<<"row:"<<i+1<<"  ";
            for(int j=0;j<fre[i].size();j++){
                cout<<fre[i][j]<<"  ";
            }
            cout<<endl;
        }
        */
        vector<int> ans(k);
        int l=0;
        for(int m=fre.size()-1;m>=0;m--){
            for(int n=0;n<fre[m].size();n++){
                ans[l]=fre[m][n];
                l++;
                if(l==k){
                    return ans;
                }
            }
        }
        return ans;
    }
};

int main(){
    //vector<int> in{1,1,1,2,2,3};
    vector<int> in{4,1,-1,2,-1,2,3};
    Solution s;
    vector<int> out=s.topKFrequent(in,2);
    for(int i=0;i<out.size();i++){
        cout<<out[i]<<"  ";
    }
    return 0;
}